package com.dubious.interview.euler.booleans;

import java.util.BitSet;

/**
 * An implementation of {@link Booleans} which uses an array of BitSets.
 * This implementation is known to use less memory than {@link ArrayedBooleans}
 * but experience shows that it is slower.
 */
public class BitSetBooleans implements Booleans
{
    BitSet[] bitSets;
    public long upperBound = 0L;
    public int arrayBoundary = Integer.MAX_VALUE;
    
    public BitSetBooleans(long upperBound)
    {
        this.upperBound = upperBound;
        
        long numArrays = (upperBound / arrayBoundary) + 1;
        if(numArrays > Integer.MAX_VALUE)
        {
            throw new RuntimeException(
                    "Cannot create Booleans with upperBound of [" 
                    + upperBound +"] because it would require too many [" 
                    + numArrays + "] arrays.");
        }
        
        bitSets = new BitSet[(int)numArrays];
        for(int i = 0; i < numArrays - 1; i++)
        {
            bitSets[i] = new BitSet(arrayBoundary);
        }
        bitSets[(int)numArrays - 1] = new BitSet((int)upperBound % arrayBoundary);
    }
    
    @Override
    public void set(long index, boolean value)
    {
        if(index > upperBound)
        {
            throw new IndexOutOfBoundsException(
                    "index [" + index + "] is greater than upper bound [" + upperBound + "]");
        }
        
        // we know it is ok to cast the get parameter to an int because we checked in the 
        // constructor that we would have number of arrays less than Integer.MAX_VALUE.
        // we know it is ok to cast the array lookup parameter to int because arrayBoundary
        // is an int
        bitSets[(int)(index / arrayBoundary)].set((int)(index % arrayBoundary), value);
    }
    
    @Override
    public boolean get(long index)
    {
        return bitSets[(int)(index / arrayBoundary)].get((int)(index % arrayBoundary));
    }
}